//给你一个整数数组 nums，请你将该数组升序排列。 
//
// 
//
// 
// 
//
// 示例 1： 
//
// 输入：nums = [5,2,3,1]
//输出：[1,2,3,5]
// 
//
// 示例 2： 
//
// 输入：nums = [5,1,1,2,0,0]
//输出：[0,0,1,1,2,5]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 50000 
// -50000 <= nums[i] <= 50000 
// 
// Related Topics 数组 分治 桶排序 计数排序 基数排序 排序 堆（优先队列） 归并排序 
// 👍 329 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {

    int[] temp;

    public int[] sortArray(int[] nums) {
        int len = nums.length;
        temp = new int[len];
        mergeSort(nums, 0, len-1);
        return nums;

    }

    public void mergeSort(int[] nums, int l, int r) {
        if (r <= l) {
            return;
        }
        if (l+1 == r) {
            if (nums[l] > nums[r]) {
                int temp = nums[l];
                nums[l] = nums[r];
                nums[r] = temp;

            }
            return;
        }
        int len = r - l + 1;
        int mid = (r + l) / 2;
        mergeSort(nums, l, mid);
        mergeSort(nums, mid + 1, r);

        int index = l;
        int ileft = l;
        int iright = mid + 1;
        while (ileft <= mid && iright <= r) {

            if (nums[ileft] > nums[iright]) {
                temp[index++] = nums[iright];
                iright++;
            } else {
                temp[index++] = nums[ileft];
                ileft++;
            }
        }

        while (iright <= r) {
            temp[index++] = nums[iright];
            iright++;
        }

        while (ileft <= mid) {
            temp[index++] = nums[ileft];
            ileft++;
        }

        for (int i = l; i <= r; i++) {
            nums[i] = temp[i];
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)
